package 二分;

/**
 * @author: TTDB
 * @create: 2025/9/22
 */
public class findMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //始终保证 nums1 的长度小于 nums2 的长度
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        //总长度---i+j=totalLeft
        int totalLeft = (m + n + 1) / 2;
        int left = 0;
        int right = m;
        //二分搜索：在 nums1 上使用二分搜索，调整 i 的位置，以满足 nums1[i-1] <= nums2[j] 和 nums2[j-1] <= nums1[i]；
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if (nums1[i - 1] <= nums2[j]) {
                left = i;
            } else {
                right = i - 1;
            }
        }
        //根据 m + n 的奇偶性来计算中位数。如果为奇数，则中位数是 max(nums1LeftMax, nums2LeftMax)；如果为偶数，
        // 则是 (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2。
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        if ((m + n) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
        }
    }
}
